백준 9527번

오늘 풀어본 문제는 백준의 9527번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

두 자연수 $A$, $B$ 가 주어졌을 때, $A \le x \le B$ 를 만족하는 모든 $x$ 에 대해 $x$ 를 이진수로 표현했을 때 $1$ 의 개수의 합을 구하는 프로그램을 작성하시오.

즉, $f(x) = x$ 를 이진수로 표현 했을 때 $1$ 의 개수라고 정의하고, 아래 식의 결과를 구하자.

\[\sum_{x=A}^{B}{f(x)}\]

입력

첫 줄에 두 자연수 $A$, $B$ 가 주어진다. $(1 \le A \le B \le 10^{16})$

출력

$1$ 의 개수를 세어 출력한다.

풀이과정

1번째 시도

문제를 해결하기 위해 사용한 방법은 다음과 같다.

$i$ 이하의 개수의 비트로 표현되는 모든 정수들의 $1$ 의 개수를 totalSetBitsUpTo2PowerN [$i$] 에 저장한다.
재귀함수 getTotalSetBitsUpToN 를 호출하여 $1$ 부터 각각 $A-1$, $B$ 까지의 모든 $1$ 의 개수를 구한 뒤, 차이를 출력한다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

vector<ull> totalSetBitsUpTo2PowerN(55, 0);

ull getTotalSetBitsUpToN(ull n);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    totalSetBitsUpTo2PowerN[0] = 0;
    for (int i=1; i<55; i++) {
        totalSetBitsUpTo2PowerN[i]
            = 2 * totalSetBitsUpTo2PowerN[i - 1] + (1ULL << (i - 1));
    }

    ull A, B;
    cin >> A >> B;

    cout << getTotalSetBitsUpToN(B) - getTotalSetBitsUpToN(A - 1);

    return 0;
}

ull getTotalSetBitsUpToN(ull n) {
    ull result = 0;
    int digitCount = 0;

    if (n == 0ULL || n == 1ULL) {
        return n;
    }
    else {
        while (n >= (1ULL << digitCount)) {
            digitCount++;
        }

        result += totalSetBitsUpTo2PowerN[digitCount - 1];

        n ^= (1ULL << (digitCount - 1));
        result += n+1;

        result += getTotalSetBitsUpToN(n);

        return result;
    }
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

오늘 문제는 상당히 어려운 문제였다. 구간의 합을 알아내는 문제라는 점에서 누적 합을 이용하는 문제라는 것까지는 알 수 있었지만, ‘어떻게’ 누적 합을 저장하고 이용해야 하는지가 까다로웠던 문제였다. 누적 합을 이용하는 방법도 꽤 다양하다는 걸 알 수 있었다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/9527

← Previous Post Next Post →